package com.zy.queue;

/**
 * Created by zhaoyi on 2019/7/31
 * https://leetcode-cn.com/explore/learn/card/queue-stack/216/queue-first-in-first-out-data-structure/865/
 * 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器
 */
public class MyCircularQueue {

    /**
     * 存放数据用
     */
    private int[] array;

    /**
     * 当前第一个元素
     */
    private int head = 0;

    /**
     * 队列尾部，入队时放这个位置
     */
    private int tail = 0;


    /**
     * 设置数组长度
     *
     * @param k
     */
    public MyCircularQueue(int k) {
        array = new int[k + 1];
    }

    /**
     * 返回是否成功
     * 插入数据，队列先进先出。
     *
     * 可以装逼优化点位运算效率高
     *  长度设为2的n次幂（假设8），利于二进制计算，例如：12%8 = 12 & (8 - 1) 即 pos = num & (size -1)
     *
     *  03 – 二进制视频
     *      链接：https://pan.baidu.com/s/1qEeJbpl7B0_UMOXAfDmCNg
     *      提取码：g289
     */
    public boolean enQueue(int value) {

        //队列满了
        if (isFull()) {
            return false;
        }
        array[tail] = value;
        tail++;
        tail = tail % array.length;
        return true;
    }

    /**
     * Delete an element from the circular queue. Return true if the operation is successful.
     */
    public boolean deQueue() {

        //空队列
        if (isEmpty()) {
            return false;
        }

        head++;
        head = head % array.length;
        return true;
    }

    /**
     * Get the front item from the queue.
     * Front: 从队首获取元素。如果队列为空，返回 -1 。
     * 只是看看不出来
     */
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return array[head];
    }

    /**
     * Get the last item from the queue.
     * Rear: 获取队尾元素。如果队列为空，返回 -1 。
     * 只是看看不出来
     */
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        int i;
        if (tail == 0) {
            i = array.length - 1;
        } else {
            i = tail - 1;
        }
        return array[i];

    }

    /**
     * Checks whether the circular queue is empty or not.
     */
    public boolean isEmpty() {
        return head == tail;

    }

    /**
     * Checks whether the circular queue is full or not.
     */
    public boolean isFull() {
        return ((head - tail) == 1 || (head == 0 && tail == array.length - 1));
    }


}
